package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseBetween(head *ListNode, m int, n int) *ListNode {
	hair := &ListNode{Next: head}
	var preBeg *ListNode = nil
	var beg *ListNode = nil
	var end *ListNode = nil
	node := head
	prev := hair
	i := 1
	for node != nil {
		if i == m {
			beg = node
			preBeg = prev
		}
		if i == n {
			end = node
			break
		}
		prev = node
		node = node.Next
		i++
	}
	preBeg.Next = doReverse(beg, end)
	return hair.Next
}

func doReverse(head *ListNode, tail *ListNode) *ListNode {
	prev := tail.Next
	n := head
	for prev != tail {
		next := n.Next
		n.Next = prev
		prev = n
		n = next
	}
	return tail
}

func main() {
	n0 := &ListNode{Val: 1}
	n1 := &ListNode{Val: 2}
	n2 := &ListNode{Val: 3}
	n3 := &ListNode{Val: 4}
	n4 := &ListNode{Val: 5}
	n0.Next = n1
	n1.Next = n2
	n2.Next = n3
	n3.Next = n4
	reverseBetween(n0, 1, 4)
}
